<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>排序算法之希尔排序</title>
</head>
<body>
  <script type="text/javascript">
    function shellSort(arr) {
      const len = arr.length;
      let gap = 1;
      while (gap < len) {
        gap = gap * 3 + 1;
      }
      while (gap > 0) {
        for (let i = gap; i < len; i++) {
          const temp = arr[i];
          let j = i - gap;
          // 跨区间排序
          while (j >= 0 && arr[j] > temp) {
            arr[j + gap] = arr[j];
            j -= gap;
          }
          arr[j + gap] = temp;
        }
        gap = Math.floor(gap / 3);
      }
    }

    const arr = [10, 6, 3, 4, 8, 1, 2];
    // const arr = [10, 8, 3, 2, 5, 9, 4, 7, 35, 47, 20];
    shellSort(arr);
    console.log(arr);
  </script>
</body>
</html>